package com.dubbo;

import com.sun.org.apache.xpath.internal.operations.Bool;

/**
 * @author caoqianhuan
 * @date 2022/9/28
 * @Description: 构建线段树 统计知为区间和
 */
public class SegmentTree {

    private int[] treeArray;

    private int[] lazy;

    private Boolean isLazy;

    private int[] data;

    public SegmentTree(int[] data, Boolean isLazy) {
        this.data = data;
        this.treeArray = new int[4 * data.length - 5];
        buildSegmentTreeWithArray(0, data.length-1, 0);
        if (isLazy) {
            lazy = new int[treeArray.length];
        }
    }

    /**
     * 构建线段树
     * @param left 原数据左边界
     * @param right 原数据右边界
     * @param treeIndex 当前节点索引
     * @return
     */
    public int buildSegmentTreeWithArray(int left, int right, int treeIndex) {
           if (left == right) {
                treeArray[treeIndex] = data[left];
                return data[left];
           }
           int mid = (left + right) >> 1;
           int leftChildNum = buildSegmentTreeWithArray(left, mid, (treeIndex << 1) + 1);
           int rightChildNum = buildSegmentTreeWithArray(mid+1, right, (treeIndex << 1) + 2);
           treeArray[treeIndex] = leftChildNum + rightChildNum;
           return leftChildNum + rightChildNum;
    }

    /**
     * 区间查询
     * @param left 要查询的取间左边界
     * @param right 要查询的区间右边界
     * @param nodeLeft  当前节点左边界
     * @param nodeRight 当前节点有右边界
     * @param nodeIndex 当前节点下标
     * @return
     */
    public int querySegment(int left, int right, int nodeLeft, int nodeRight, int nodeIndex) {
           if (left == nodeLeft && right == nodeRight) {
               return treeArray[nodeIndex];
           }
           int res = 0;
           int mid = (nodeLeft + nodeRight) >> 1;
           if (left > mid) {
               res += querySegment(left, right, mid+1, nodeRight, (nodeIndex << 1) + 2);
           }
           else if (right <= mid) {
                res += querySegment(left, right, nodeLeft, mid, (nodeIndex << 1) + 1);
           } else {
               res += querySegment(left, mid, nodeLeft, mid, (nodeIndex << 1) + 1);
               res += querySegment(mid+1, right, mid+ 1, nodeRight, (nodeIndex << 1) + 2);
           }

           return  res;
    }

    /**
     * 单点更新
     * @param addVal 需要添加的值（或者说是需要修改的值 更具具体情况）
     * @param rectifyIndex 需要更新点的坐标
     * @param nodeLeft 当前节点的左边界
     * @param nodeRight 当前节点的右边界
     * @param nodeIndex 当前节点的索引值
     */
    public void rectifyDot(int addVal, int rectifyIndex, int nodeLeft, int nodeRight, int nodeIndex) {
        if ((nodeLeft == nodeRight) && (nodeLeft == rectifyIndex)) {
            data[rectifyIndex] += addVal;
            treeArray[nodeIndex] += addVal;
            return;
        }
        int mid = (nodeLeft + nodeRight) >> 1;
        if (rectifyIndex <= mid) {
            rectifyDot(addVal, rectifyIndex, nodeLeft, mid, (nodeIndex << 1) + 1);
        } else {
            rectifyDot(addVal, rectifyIndex, mid+1, nodeRight, (nodeIndex << 1) + 2);
        }
        treeArray[nodeIndex] += addVal;
    }

    /**
     * 区间更新 非懒惰
     * @param addVal 需要附加的值
     * @param rectifyLeft 更新区间的左边界
     * @param rectifyRight 更新区间的右边界
     * @param nodeLeft 当前节点左边界
     * @param nodeRight 当前节点右边界
     * @param nodeIndex 当前节点的索引值
     */
    public void rectifySegment(int addVal, int rectifyLeft, int rectifyRight, int nodeLeft, int nodeRight, int nodeIndex) {
        if ((rectifyLeft == nodeLeft) && (rectifyRight == nodeRight)) {
            for (int i = rectifyLeft; i <= rectifyRight; i++) {
                data[i] += addVal;
            }
            treeArray[nodeIndex] += addVal * (rectifyRight - rectifyLeft + 1);
            //更新子节点
            if (nodeLeft == nodeRight) {
                treeArray[nodeIndex] += addVal;
                return;
            }
            int mid = (nodeLeft + nodeRight) >> 1;
            rectifySegment(addVal, nodeLeft, mid, nodeLeft, mid, (nodeIndex << 1) + 1);
            rectifySegment(addVal, mid+1, nodeRight, mid+1, nodeRight, (nodeIndex << 1) + 2);
            return;
        }
        int mid = (nodeLeft + nodeRight) >> 1;
        if (rectifyLeft > mid) {
            rectifySegment(addVal, rectifyLeft, rectifyRight, mid+1, nodeRight, (nodeIndex << 1) + 2);
            treeArray[nodeIndex] += addVal * (rectifyRight - rectifyLeft + 1);
        } else if (rectifyRight <= mid) {
            rectifySegment(addVal, rectifyLeft, rectifyRight, nodeLeft, mid, (nodeIndex << 1) + 1);
            treeArray[nodeIndex] += addVal * (rectifyRight - rectifyLeft + 1);
        } else {
            rectifySegment(addVal, rectifyLeft, mid, nodeLeft, mid, (nodeIndex << 1) + 1);
            treeArray[nodeIndex] += addVal * (mid - rectifyLeft + 1);
            rectifySegment(addVal, mid+1, rectifyRight, mid+1, nodeRight, (nodeIndex << 1) + 2);
            treeArray[nodeIndex] += addVal * (rectifyRight - mid);
        }
    }

    /**
     * 懒惰区间更新
     * @param addVal
     * @param rectifyLeft
     * @param rectifyRight
     * @param nodeLeft
     * @param nodeRight
     * @param nodeIndex
     */

    public void lazyDown(int nodeIndex) {
        if (lazy[nodeIndex] > 0) {
            treeArray[(nodeIndex << 1)+1] += lazy[nodeIndex];
            treeArray[(nodeIndex << 1)+2] += lazy[nodeIndex];
            lazy[(nodeIndex << 1)+1] = lazy[nodeIndex];
            lazy[(nodeIndex << 1)+2] = lazy[nodeIndex];
            lazy[nodeIndex] = 0;
        }
    }
    public void rectifySegmentLazy(int addVal, int rectifyLeft, int rectifyRight, int nodeLeft, int nodeRight, int nodeIndex) {
        if (nodeLeft <= rectifyLeft && nodeRight <= rectifyRight) {
            treeArray[nodeIndex] += addVal * (rectifyRight - rectifyLeft + 1);
            lazy[nodeIndex] = addVal * (rectifyRight - rectifyLeft + 1);
            return;
        }
        lazyDown(nodeIndex);
        int mid = (nodeLeft + nodeRight) >> 1;
        if (rectifyLeft < mid) {
            //rectifySegment(addVal, rectifyLeft, rectifyRight, );
        }
    }

    public static void main(String[] args) {
        int[] data = new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8};

        SegmentTree segmentTree = new SegmentTree(data, false);
        segmentTree.buildSegmentTreeWithArray(0, data.length - 1, 0);
        for (int nodeVal : segmentTree.treeArray) {
            System.out.printf("%1$d, ", nodeVal);
        }
        System.out.println("\n" + segmentTree.querySegment(0, 5, 0, data.length - 1, 0));

        //segmentTree.rectifyDot(1, 4, 0, data.length-1, 0);
        //for (int nodeVal : segmentTree.treeArray) {
        //    System.out.printf("%1$d, ", nodeVal);
        //}

        segmentTree.rectifySegment(1, 3, 6, 0, data.length-1, 0);
        for (int nodeVal : segmentTree.treeArray) {
            System.out.printf("%1$d, ", nodeVal);
        }
    }
}
